//! By convention, root.zig is the root source file when making a library. If
//! you are making an executable, the convention is to delete this file and
//! start with main.zig instead.
const std = @import("std");
const testing = std.testing;
const dprint = std.debug.print;

pub export fn add(a: i32, b: i32) i32 {
    return a + b;
}

test "basic add functionality" {
    try testing.expect(add(3, 7) == 10);
}
// 比较函数：按数值升序
fn lessThan(_: void, a: f64, b: f64) std.math.Order {
    return std.math.order(a, b);
}
test "priority dequeue " {
    const PDF = std.PriorityDequeue(f64, void, lessThan);
    var que = PDF.init(std.testing.allocator, {});
    defer que.deinit();
    try que.add(54);
    try que.add(12);
    try que.add(7);
    try que.add(23);
    try testing.expectEqual(@as(u32, 7), que.removeMin()); // 最小
    try testing.expectEqual(@as(u32, 12), que.removeMin());
    try testing.expectEqual(@as(u32, 23), que.removeMin());
    try testing.expectEqual(@as(u32, 54), que.removeMin());
}

test "array list" {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    var list = std.ArrayList(f64).init(arena.allocator());
    defer list.deinit();

    dprint("{}\n", .{@sizeOf(@TypeOf(list))});

    try list.append(8);
}
// zig的优先队列就是堆结构体
test "array list unmanaged" {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();
    var list = std.ArrayListUnmanaged(i32).empty;
    // var list = std.ArrayList(f64).init(arena.allocator());
    defer list.deinit(allocator);

    try list.append(allocator, 5);
    dprint("unmanaged {}\n", .{@sizeOf(@TypeOf(list))});

    // try list.append(8);
}

test "doubly linked list" {
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();
    const L = std.DoublyLinkedList(u32);
    var node_list = L{};
    const one_node = try allocator.alloc(L.Node, 1);
    one_node[0] = L.Node{
        .data = 3,
    };
    node_list.append(&(one_node[0]));
    const popped = node_list.pop();
    try std.testing.expect(popped != null);
    try std.testing.expect(popped.?.data == 3);
}

test "doubly linked list1" {
    // 使用 ArenaAllocator 自动管理内存
    var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator);
    defer arena.deinit();
    const allocator = arena.allocator();

    // 定义链表类型
    const L = std.DoublyLinkedList(u32);
    var node_list = L{};

    // 动态创建节点（推荐方式）
    const one = try allocator.create(L.Node);
    one.* = .{ .data = 1 };

    const two = try allocator.create(L.Node);
    two.* = .{ .data = 2 };

    const three = try allocator.create(L.Node);
    three.* = .{ .data = 3 };

    // 插入节点：构建 [1, 2, 3]
    node_list.append(one);
    node_list.append(two);
    node_list.append(three);

    // ✅ 断言链表长度
    try std.testing.expectEqual(@as(usize, 3), node_list.len);

    // ✅ 断言头尾
    try std.testing.expect(node_list.first == one);
    try std.testing.expect(node_list.last == three);

    // ✅ 正向遍历检查
    {
        var it = node_list.first;
        const expected = [_]u32{ 1, 2, 3 };
        for (expected) |value| {
            try std.testing.expect(it != null);
            try std.testing.expect(it.?.data == value);
            it = it.?.next;
        }
        try std.testing.expect(it == null); // 遍历结束
    }

    // ✅ 反向遍历检查
    {
        var it = node_list.last;
        const expected = [_]u32{ 3, 2, 1 };
        for (expected) |value| {
            try std.testing.expect(it != null);
            try std.testing.expect(it.?.data == value);
            it = it.?.prev;
        }
        try std.testing.expect(it == null);
    }

    // ✅ 删除中间节点（two）
    node_list.remove(two);
    try std.testing.expectEqual(@as(usize, 2), node_list.len);

    // 再次遍历：应为 [1, 3]
    {
        var it = node_list.first;
        try std.testing.expect(it != null and it.?.data == 1);
        it = it.?.next;
        try std.testing.expect(it != null and it.?.data == 3);
        try std.testing.expect(it.?.next == null);
    }

    // ✅ 弹出最后一个元素
    const popped = node_list.pop();
    try std.testing.expect(popped != null);
    try std.testing.expect(popped.?.data == 3);

    // ✅ 弹出第一个元素
    const popped_first = node_list.popFirst();
    try std.testing.expect(popped_first != null);
    try std.testing.expect(popped_first.?.data == 1);

    // 链表应为空
    try std.testing.expect(node_list.first == null);
    try std.testing.expect(node_list.last == null);
    try std.testing.expect(node_list.len == 0);
    try std.testing.expect(node_list.pop() == null);
    try std.testing.expect(node_list.popFirst() == null);
}
